package leetcode.day_2021_03_22_2021_03_28;

import java.util.Arrays;

/**
 * 75. 颜色分类
 * https://leetcode-cn.com/problems/sort-colors/
 */
public class LeetCode0075 {

    public static void sortColors(int[] nums) {
        int length = nums.length;
        if (length == 0) {
            return;
        }
        int front = 0, end = length-1, i0 = 0;
        while (front <= end) {
            if (nums[front] == 2) {
                swap(front, end, nums);
                end-=1;
            } else if (nums[front]==0) {
                if (i0 == front) {
                    front++;
                    i0++;
                } else {
                    swap(front, i0, nums);
                    i0++;
                }
            } else {
                front++;
            }
        }
    }

    public static void swap(int front, int end, int[] nums) {
        int temp = nums[front];
        nums[front] = nums[end];
        nums[end] = temp;
    }

    public static void sortColors2(int[] nums) {
        int n0 = 0, n1 = 0;
        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            nums[i] = 2;
            if(num < 2){
                nums[n1++] = 1;
            }
            if(num < 1){
                nums[n0++] = 0;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,0,2,1,1,0};
        sortColors2(arr);
        System.out.println(Arrays.toString(arr));
    }
}
